The present invention relates to signal processing and, more particularly, to techniques for determining the location of a signal receiver.
The location of a device may be determined using a global positioning system (xe2x80x9cGPSxe2x80x9d). In a general GPS system, a receiver acquires signals from four or more satellite vehicles to obtain a three dimensional location and a time stamp. A receiver may employ multiple channels and the received signal in each channel may be used to acquire a signal from a single signal source. After acquisition, a delay-locked loop is traditionally used to track the signal source and is used to give updates to the receiver position through time. GPS satellite vehicles emit two microwave carrier signals of L1 and L2 frequency. The two microwave carrier signals are modulated by: 1) a C/A code (Coarse Acquisition), 2) a P-Code (Precise), and 3) a data message.
The C/A code is a repeating 1 MHz Pseudo Random Noise (PRN) code that modulates the signal at frequency L1. The C/A PRN code comprises 1023 bits of information that is repeated every millisecond. There is a different C/A PRN code for each GPS satellite vehicle. The P-Code modulates the signals at both the L1 and L2 frequencies. The P-Code is a 10 MHz PRN code. The data message modulates the L1-C/A code signal. The data message is a 50 Hz signal consisting of data bits, also known as xe2x80x9cnavigation bitsxe2x80x9d, that give a time stamp, describe the GPS satellite vehicle orbits, clock corrections, and other parameters. All of this data is useful for the receiver to know in order to calculate and update its position. In traditional GPS systems, this data is decoded from the signal after the signal has been acquired and acquisition is carried out without the benefit of knowing this data.
In one approach, a receiver may attempt to acquire a signal by: 1) generating a replica of the PRN code emitted by a satellite vehicle that is potentially visible overhead the receiver, and 2) determining a correlation between the received signal and a suitable modulated replica code. Typically, the correlation between the received signal and the replica code is performed by calculating the In Phase (xe2x80x9cIxe2x80x9d) and Quadrature (xe2x80x9cQxe2x80x9d) correlation integrals. One issue that arises is that the signal from the satellite is also modulated by data bits using phase modulation. These data bits are unknown at a standard stand-alone receiver before acquisition and as a result, the I and Q correlation integrals can not be extended coherently beyond the length of one data bit. One existing approach around this problem is to combine the I and Q correlation integrals non-coherently between data bits. This also helps to mitigate the impact of uncertainty in the carrier modulation frequency.
One salient disadvantage to the non-coherent approach is that in instances when the received signal is highly attenuated (for example, if the receiver that is receiving the received signal is in a building), the duration of data needed to compensate for the level of attenuation increases with the level of attenuation at a much faster rate than it does under a coherent approach.
The uncertainty in the carrier modulation frequency arises from two primary sources. The first is the net movement of the individual signal source relative to the receiver. In the case of GPS, the signal source is a satellite moving at a speed of a few thousand meters every second while the receiver may also be moving at a usually slower but usually unknown speed. In the case of GPS, the velocity of the satellite can be calculated to very high accuracy by the receiver once it has access to the current orbital parameters of the satellite in question and the current time. The motion of the signal source and the motion of the receiver introduce a Doppler shift that effectively compresses or dilates the signal in time, resulting in a change in modulation frequency as well. The second major source of frequency uncertainty is the imperfect syntony between the clock on the receiver and the clock in the signal source. Since the signal source clock and the receiver clock are generally distinct, there is a net slowing-down or speeding-up of time between the signal source and the receiver. This clock drift of the receiver relative to the source is also experienced as a compression or dilation of the signal at the receiver and is herein referred to as xe2x80x9cclock Doppler.xe2x80x9d
In addition to the frequency uncertainty, there is an uncertainty introduced due to the unknown propagation delay from the signal source to the receiver. The speed of light is finite and hence it takes a finite time proportional to the distance between the source and the receiver for the signal to arrive at the receiver after being transmitted at the source.
The initial problem of acquiring a signal therefore involves a search over the exact modulation frequency and the delay to the signal source. The pseudorandom structure underlying the signal ensures that the correlation integrals will be relatively small if either the modulation frequency or the delay is substantially different from the true value. Finally, the repeating nature of the PRN code implies that the delay value provides range information only modulo the time of repetition, unless a priori knowledge about the data bits is used.
In traditional positioning systems, the problem of acquisition is solved mostly independently for the different signal sources. Each channel successively tests different delay and frequency hypotheses, and computes I and Q correlations for them. When a sufficiently high value is found, it is tracked for a while and the receiver attempts to decode the data bits. Different channels may be allocated to search for different signal sources, but there is no substantial interaction between the different searches during the acquisition phase. A significant disadvantage of the above approach to acquisition is that it might have to search for a long amount of time before it has acquired enough signals to proceed. The longer the duration of coherent integration, the more finely the modulation frequency has to be known. The more attenuated the signal, the longer the duration of computing the correlations at any given frequency and delay pair must be before the signal can be discriminated from the noise. These two problems combine to make search in attenuated environments prohibitively expensive in terms of either required delays or the number of independent channels needed to acquire the signals. Furthermore, the independence of the channels for each signal in the acquisition phase does not leverage the calculations for the clock Doppler and delay values performed with respect to one signal source to aid the calculations with respect to another signal source.
After acquisition, in traditional GPS, the distance to each satellite is estimated by decoding the time stamp information embedded in the data message and comparing it to the time of reception by the receiver""s own clock. The result of this comparison is traditionally referred to as a xe2x80x9cpseudorangexe2x80x9d and is expressed in meters rather than seconds by multiplying by the speed of light. Any net drift due to the imperfect synchronization of the two clocks is corrected for through a space/time triangulation procedure combining the pseudoranges from four or more signal sources. This procedure also results in an initial position estimate. This estimate is then updated through time using the outputs of delay locked loops tracking the received signals. This approach suffers from the drawback of having to wait for the time-stamp in the data message before giving even an initial position fix. In traditional GPS, the time stamps are transmitted only once every few seconds. This means that even if the receiver is able to acquire all the satellites instantly, it still might have to wait up to a few seconds before being able to give any position estimate at all.
Some of these difficulties are partially mitigated by the techniques of assisted GPS but many of them remain problematic, especially in challenging attenuated environments such as urban buildings. In such environments, the existing assisted GPS technologies become impractical due to the computation expense and/or the need for very long sampling times.
Based on the foregoing, there is a clear need for a technique to determine the location of the receiver that requires less computational expense and can operate with a shorter duration of data.
Techniques are provided for determining the location of a signal receiver based on sampled data arising from a received signal that contains location-determining signals and noise. According to one aspect of the invention, segments of sampled data of increasing length are examined in sequence. Bounds for the delay value and bounds for the modulation frequency value of the received signal are calculated for each signal source from a set of signal sources that are presumed detectable at the signal receiver. An estimate (xe2x80x9cnominal valuexe2x80x9d) for the delay value, a value range for the delay value, an estimate for the modulation frequency value, and a value range for the modulation frequency value are calculated by iteratively updating the current bounds for the delay value and for the modulation frequency value. The iterative update of the current value range for the delay value and for the modulation frequency value is performed over the set of signal sources and over the segments of data of increasing length. The results obtained from the calculations for one acquired signal source and one segment are used to refine the estimates for another source.
According to another aspect of the invention, a threshold that a calculated correlation magnitude needs to exceed for the signal source to be considered acquired is set according to the widths of the corresponding delay value range and modulation frequency range. This threshold is set by using a statistical method that takes into account the probability that a false acquisition arises within the delay value range and modulation frequency value range. Wide ranges increase the probability of a false acquisition, and therefore raise the acquisition threshold.
According to another aspect of the invention, for each signal source, coherent I and Q correlation integrals are synthesized and their magnitude values are calculated corresponding to various choices for the delay value and for the modulation frequency value, within a search range determined by the current bounds and value ranges. The choices for the delay value and for the modulation frequency are initially made at a coarse scale. In addition, for each signal source that is acquired, I and Q correlation integrals and their magnitude values are calculated corresponding to a set of delay values and modulation frequency values that surround the best current estimate of the delay value and the modulation frequency value. The fine scale shape of the magnitude-curve is estimated using interpolated values corresponding to the estimate of the delay value and the estimate of the modulation frequency value and corresponding to the set of delay values and the set of modulation frequency values that surround the current estimates thereof.
According to another aspect of the invention, the location, time, and other variables of interest related to the receiver are calculated using the shape of the magnitude curve to represent the I and Q correlation integrals for each signal source. Other bounds are calculated to estimate the quality of these estimates and can be used to terminate the algorithm when a sufficiently high quality is reached.